f[i][j][k]+=f[i-1][j][k]

f[i][j+1][k] += f[i-1][j][k]*(m-j-k)
f[i][j-1][k+1] += f[i-1][j][k]*j

void update(int rt) {
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
	sum_square[rt]=sum_square[rt<<1]+sum_square[rt<<1|1];
	ans[rt]=(sum[rt]*sum[rt]-sum_square[rt])/2
}

void update(int rt) {
	ans[rt]=max(max(ans[rt<<1],ans[rt<<1|1]),sum_suf[rt<<1]+sum_pre[rt<<1|1]);
	sum_pre[rt]=max(sum_pre[rt<<1],sum[rt<<1]+sum_pre[rt<<1|1]);
	sum_suf[rt]=max(sum_suf[rt<<1|1],sum[rt<<1|1]+sum_suf[rt<<1]);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void color(int l,int r,int rt,int c) {
	if (c>=0) {
		ans[rt]=sum_suf[rt]=sum_pre[rt]=sum[rt]=(r-l+1)*c;
	}
	else {
		ans[rt]=sum_suf[rt]=sum_pre[rt]=0;
		sum[rt]=(r-l+1)*c;
	}
}


void color(int l,int r,int rt,int a,int b) {
	sum[rt] += (r-l+1)*a + (r-l+1)*(r-l)/2*b;

	col[rt][1] += a;
	col[rt][2] += b;
}

void push_col(int l,int r,int rt) {
	if (col[rt][1] || col[rt][2]) {
		int m=(l+r)>>1;
		color(lson,col[rt][1],col[rt][2]);
		color(rson,col[rt][1]+col[rt][2]*(m-l+1),col[rt][2]);
		col[rt][1]=col[rt][2]=0;
	}
}

#define lson l,m,z[rt].l
#define rson m+1,r,r

void update(int rt) {
	z[rt].sum=z[z[rt].l].sum+z[z[rt].r].sum;
}

int cnt=0;
struct node {
	int l,r,sum;
}z[maxn];

int modify(int l,int r,int rt,int p,int v) {
	int new_rt = ++ cnt;
	z[new_rt]=z[rt];
	if (l==r) {
		z[new_rt].sum=v;
		return new_rt;
	}
	int m=(l+r)>>1;
	if (p<=m) z[new_rt].l=modify(lson,p,v);
	else z[new_rt].r=modify(rson,p,v);
	update(new_rt);
	return new_rt;
}

int root[maxn];

root[0]=build(1,n,1);
for (int a=1;a<=m;a++)
	root[a]=modify(1,n,root[a-1],p,v);
root[k]

#define lb(x) ((x)&(-(x)))
void modify(int p,int v) {
	for (;p<=n;p+=lb(p))
		z[p]+=v;
}
int query(int p) {
	int ans=0;
	for (;p;p-=lb(p))
		ans+=z[p];
	return ans;
}

y
for (int a=1;a<=n;a++)
	modify(a,y[a]);

l,r
query(r)-query(l-1);






